package com.zlk.algorithm.bit.xor;

import org.junit.Test;

import java.util.Arrays;

/**
 * @program: algorithm
 * @ClassName Demo
 * @description:
 * @author: slfang
 * @create: 2023-12-11 10:06
 * @Version 1.0
 **/
public class Demo {
    private int[] arr = new int[]{2,3,1,10,5,7,4};

    /**
     * @description: ^ 异或运算  相同为0，不同为1
     * 1）0^N == N N^N == 0
     * 2）异或运算满足交换律和结合率
     * 3）不用额外变量交换两个数
     * @author: fsl
     * @date: 2022/8/15 15:10
     **/
    @Test
    public void test1(){
        swap(arr,0,0);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * @description:  交换方法的升级版本 没有额外空间的开销，但是注意 i=j  也就是交换的数据不能是
     * 同一个内存空间当为一个空间的话就置为0
     * 异或运算的性质与扩展
     *    1）0^N == N N^N == 0
     *    2）异或运算满足交换律和结合率
     *    3）不用额外变量交换两个数
     * @author: fsl
     * @date: 2022/8/15 15:00
     * @param: arr
     * @param: i
     * @param: j
     **/
    public static void swap(int[] arr, int i, int j) {
        // a=a^b   b=b
        arr[i] = arr[i] ^ arr[j];
        // b=a^b^b=a
        arr[j] = arr[i] ^ arr[j];
        // a=a^b^a=b
        arr[i] = arr[i] ^ arr[j];
    }

    /**
     * @description: 1、一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个
     *               2、一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数
     * @author: fsl
     * @date: 2022/8/15 15:20
     **/
    @Test
    public void String() {
        int a = 5;
        int b = 7;
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println(a);
        System.out.println(b);
        int[] arr1 = { 3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };
        printOddTimesNum1(arr1);

        int[] arr2 = { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };
        printOddTimesNum2(arr2);
    }

    public  void printOddTimesNum1(int[] arr) {
        int eO = 0;
        for (int cur : arr) {
            eO ^= cur;
        }
        System.out.println(eO);
    }

    public  void printOddTimesNum2(int[] arr) {// ab
        int eO = 0, eOhasOne = 0;
        for (int curNum : arr) {
            eO ^= curNum;
        }
        //假设 2个奇数分别是a b  此时 eO  = a^b
        // 因为 a b不相等  所有  e0 肯定有一位上存在1  所以我们可以把数组分为两类 某位上存在1 的某位置上不存在1 的
        //找最右测为1的数
        //https://blog.csdn.net/Unknownfuture/article/details/104673639
        int rightOne = eO & (~eO + 1);
        for (int cur : arr) {
            if ((cur & rightOne) != 0) {
                eOhasOne ^= cur;
            }
        }
        System.out.println(eOhasOne + " " + (eO ^ eOhasOne));
    }

}
